package Graph.TopoSort;

import java.util.LinkedList;

public class DFS {
    private int v;
    private LinkedList<Integer> adj[];
    boolean found = false;

    public DFS(int v) {
        this.v = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new LinkedList<>();
        }
    }

    public void addEdge(int s, int t) {
        adj[s].add(t);
        adj[t].add(s);
    }

    public void topoSortByDFS() {
        //先构建逆邻接表，s->t表示s依赖于t，s后于t执行
        LinkedList<Integer>[] inverseAdj = new LinkedList[v];
        for (int i = 0; i < v; i++) {//申请空间
            inverseAdj[i] = new LinkedList<>();
        }
        for (int i = 0; i < v; i++) {//通过邻接表生成逆邻接表
            for (int j = 0; j < adj[i].size(); j++) {
                int w = adj[i].get(j);//i->w
                inverseAdj[w].add(i);
            }
        }
        boolean[] visited = new boolean[v];
        for (int i = 0; i < v; i++) {//深度优先遍历图
            if (visited[i] == false) {
                visited[i] = true;
                dfs(i, inverseAdj, visited);
            }
        }
    }

    private void dfs(int vertex, LinkedList<Integer>[] inverseAdj, boolean[] visited) {
        for (int i = 0; i < inverseAdj[vertex].size(); i++) {
            int w = inverseAdj[vertex].get(i);
            if (visited[w] == true) continue;
            visited[w] = true;
            dfs(w, inverseAdj, visited);
        }
        //先把它依赖的所有顶点输出，再输出自己
        System.out.print("->" + vertex);
    }
}
